package cn.cxq.learning.single_linked_list;

import java.util.Stack;

/**
 * 单链表
 */
public class SingleLinkedList {

    private Node head;

    public SingleLinkedList(){
        this.head = new Node(0,"");
    }

    /**
     * 直接在末尾添加
     * @param node
     */
    public void add(Node node){
        Node temp = this.head;
        while (temp.nest != null){
            temp = temp.nest;
        }
        temp.nest = node;
        System.out.println("插入成功~~~");
    }

    /**
     * 按编号添加，如果有重复的就不给添加
     * @param node
     */
    public void addByOrder(Node node){
        Node temp = this.head;
        while (temp.nest != null){
            if (temp.nest.no > node.no) break;
            if (temp.nest.no == node.no) {
                System.out.println("编号已存在，无法插入节点~~~");
                return;
            }
            temp = temp.nest;
        }
        node.nest = temp.nest;
        temp.nest = node;
        System.out.println("插入成功~~~");
    }

    public void delete(int no){
        Node temp = this.head;
        if (temp.nest == null) {
            System.out.println("链表为空~~~");
            return;
        }
        while (temp.nest != null){
            if (temp.nest.no == no) break;
            temp = temp.nest;
        }
        if (temp.nest!=null){
            temp.nest = temp.nest.nest;
            System.out.println("删除成功~~~");
        }else System.out.println("删除失败，未找到节点~~~");
    }

    public void update(Node node){
        Node temp = this.head;
        if (temp.nest == null) {
            System.out.println("链表为空~~~");
            return;
        }
        while (temp.nest != null){
            if (temp.nest.no == node.no) break;
            temp = temp.nest;
        }
        if (temp.nest!=null){
            node.nest = temp.nest.nest;
            temp.nest = node;
            System.out.println("修改成功~~~");
        }else System.out.println("修改失败，未找到节点~~~");
    }

    public void list(){
        Node temp = this.head;
        if (temp.nest == null) {
            System.out.println("链表为空~~~");
            return;
        }
        while (temp.nest != null){
            temp = temp.nest;
            System.out.println(temp);
        }
    }

    //面试题：有效节点的个数
    public int length(){
        int length = 0;

        Node temp = head;
        while (temp.nest != null){
            length ++;
            temp = temp.nest;
        }

        return length;
    }

    //面试题：倒数第k个节点
    public Node lastIndexNode(int index){

        Node temp = head;
        if (head.nest == null) {
            throw new NullPointerException("链表为空~~~");
        }

        int length = 0;
        while (temp.nest != null){
            length ++;
            temp = temp.nest;
        }

        if (index <= 0 || index > length){
            throw new NullPointerException("不存在这样一个节点~~~");
        }

        temp = head.nest;

        for (int i = 0; i < length - index; i++) {
            temp = temp.nest;
        }

        return temp;
    }

    //腾讯面试题，单链表反转
    public void reverse(){

        SingleLinkedList reverseList = new SingleLinkedList();


        if (head.nest == null || head.nest.nest == null){
            return;
        }

        Node cur =this.head.nest;
        Node temp; //临时存储cur的下一个节点

        while (cur != null){
            temp = cur.nest;
            cur.nest = reverseList.head.nest;
            reverseList.head.nest = cur;
            cur = temp;
        }


       this.head = reverseList.head;
    }

    //百度面试题：反转打印
    public void reversePrint(){
        if (head.nest == null){
            return;
        }

        //压栈
        Stack<Node> stack = new Stack<>();
        Node cur = head.nest;
        while (cur != null){
            stack.add(cur);
            cur = cur.nest;
        }

        //出栈
        while (stack.size() != 0){
            System.out.println(stack.pop());
        }
    }
}

class Node{

    int no;
    String msg;
    Node nest;

    public Node(int no, String msg) {
        this.no = no;
        this.msg = msg;
        this.nest = null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", msg='" + msg +
                '}';
    }
}
